package leetCode.offer07;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 * 示例 1:
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 * 示例 2:
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *
 * 限制：
 * 0 <= 节点个数 <= 5000
 */
public class Solution1 implements Solution {

    /**
     * 此解法使用前序，中序子数组划分，通过递归进行树的构建的
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @return 重构的根节点
     */
    @Override
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        if(preorder.length==1) return root;
        int index = 0;
        for(int i=0;i<inorder.length;i++) {
            if(preorder[0]==inorder[i]) {
                index = i;
                break;
            }
        }

        int[] leftPreorder = new int[index];
        int[] leftInorder = new int[index];
        int[] rightPreorder = new int[inorder.length-index-1];
        int[] rightInorder = new int[inorder.length-index-1];

        for(int i=0;i<index;i++) {
            leftPreorder[i] = preorder[i+1];
            leftInorder[i] = inorder[i];
        }
        for(int i=0;i<inorder.length-index-1;i++) {
            rightInorder[i] = inorder[index+1+i];
            rightPreorder[i] = preorder[index+1+i];
        }

        root.left = buildTree(leftPreorder,leftInorder);
        root.right = buildTree(rightPreorder,rightInorder);

        return root;
    }


    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        System.out.println(new Solution1().buildTree(preorder,inorder));
    }





}
